Binary Tree

Types of Binary Trees

Full Binary Tree

Every node has either:

• 0 children (leaf)
• OR 2 children

      1
     / \
    2   3
       / \
      4   5

Complete Binary Tree

All levels are completely filled except possibly the last level, and nodes are filled from left to right.

        1
       / \
      2   3
     / \
    4   5

Perfect Binary Tree

All internal nodes have 2 children AND all leaves are at the same level.

        1
       / \
      2   3
     / \  / \
    4  5 6   7

Degenerate (Skewed) Binary Tree

Every parent has only one child.

Example (Right Skewed):

1
 \
  2
   \
    3

Balanced Binary Tree

Height difference between left and right subtree is minimal (usually ≤ 1).

This keeps the tree height close to log₂(n), making operations efficient.

        10
       /  \
      5    15
     / \     \
    3   7     20

Binary Search Tree

A special binary tree where:

• Left subtree contains values less than the node.
• Right subtree contains values greater than the node.

        8
       / \
      3   10
     / \    \
    1   6     14
       / \    /
      4   7  13

Traversal

• DFS: Inorder, Preorder, Postorder
• BFS

void levelOrder(Node* root) {

    if(root == NULL){
        return;
    }
    
    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* current = q.front();
        q.pop();

        cout << current->data << " ";

        if (current->left != NULL){
            q.push(current->left);
        }

        if (current->right != NULL){
            q.push(current->right);
        }
    }
};